package bit1;
import java.util.*;
class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
         this.left = left;
          this.right = right;
      }
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null){
            return root2;
        }
        else if(root2==null){
            return root1;
        }
        root1.val+=root2.val;
        root1.left=mergeTrees(root1.left,root2.left);
        root1.right=mergeTrees(root1.right,root2.right);
        return root1;
    }
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        inorder(root, res);
        TreeNode one=new TreeNode(-1);
        TreeNode tow=one;
        int count=0;
        while(count<res.size()){
            tow.right=new TreeNode(res.get(count++));
            tow=tow.right;
        }
        return one.right;
    }
    public void inorder(TreeNode node, List<Integer> res){
        if(node==null){
            return;
        }
        inorder(node.left,res);
        res.add(node.val);
        inorder(node.right,res);
    }
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftDepth=maxDepth(root.left);
        int rightDepth=maxDepth(root.right);
        if(leftDepth>rightDepth){
            return leftDepth+1;
        }
        return rightDepth+1;
    }
    public List<Integer> preorderTraversal(TreeNode root) {
          List<Integer> ret=new LinkedList<>();
          if (root==null){
              return ret;
          }
          ret.add(root.val);
          List<Integer> left=new LinkedList<>(preorderTraversal(root.left));
          ret.addAll(left);
          List<Integer> right=new LinkedList<>(preorderTraversal(root.right));
          ret.addAll(right);
          return ret;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret=new LinkedList<>();
        if (root==null){
            return ret;
        }
       //
        List<Integer> left=inorderTraversal(root.left);
        //ret.add(root.val);
        ret.addAll(left);
        List<Integer> right=inorderTraversal(root.right);
        ret.addAll(right);
        return ret;
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret=new LinkedList<>();
        if (root==null){
            return ret;
        }
        List<Integer> left=inorderTraversal(root.left);
        ret.addAll(left);
        List<Integer> right=inorderTraversal(root.right);
        ret.addAll(right);
        ret.add(root.val);
        return ret;
    }
    int getSize2(TreeNode root){
        if(root==null){
            return 0;
        }
        return getLeafSize2(root.left)+getLeafSize2(root.right)+1;
    }
    int getLeafSize2(TreeNode root){
          if(root==null){
              return 0;
          }
          if (root.left==null&&root.right==null){
              return 1;
          }
          return getLeafSize2(root.right)+getLeafSize2(root.left);
    }
    int getKLevelSize(TreeNode root,int k){
          if(root==null||k==0){
              return 0;
          }
          if(k==1){
              return 1;
          }
          return getKLevelSize(root.left, k)+getKLevelSize(root.right, k-1);
    }
    TreeNode find(TreeNode root, int val){
          if(root==null){
              return null;
          }
          if (root.val==val){
              return root;
          }
          TreeNode ret=find(root.left,val);
          if (ret!=null){
              return ret;
          }
          ret=find(root.right,val);
        if (ret!=null){
            return ret;
        }
        return null;
    }
    public void preOrderNRec(TreeNode root){
          Stack<TreeNode> stack=new Stack<>();
          if (root==null){
              return;
          }
          stack.add(root);
          while (!stack.isEmpty()){
              TreeNode node=stack.pop();
              System.out.println(node.val);
              if(node.right!=null){
                  stack.add(node.right);
              }
              if(node.left!=null){
                  stack.add(node.left);
              }
          }
    }
    public void inOrderNRec(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        if (root==null){
            return;
        }
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.add(root);
                root=root.left;
            }
            if (!stack.isEmpty()){
                root=stack.pop();
                System.out.println(root.val);
                root=root.right;
            }
        }
    }
    public static void recursivePostOrder(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        if (root==null){
            return;
        }
        TreeNode prev=null;
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.add(root);
                root=root.left;
            }
            if(!stack.isEmpty()){
                root=stack.peek();
                if(root.right==null||prev==root.right){
                    root=stack.pop();
                    System.out.println(root.val);
                    prev=root;
                    root=null;
                }
                else {
                    root=root.right;
                }
            }
        }
    }
}
class home4 {
    public static void main(String[] args) {
        TreeNode node2=new TreeNode(2);
        TreeNode node3=new TreeNode(3);
        TreeNode node1=new TreeNode(1,node2,node3);
        node1.recursivePostOrder(node1);
    }
}
